#include "BinaryTree.h"
#include "Binary_Tree_i.h"

#include <string.h>
#include <stdlib.h>


/*********************************** 
       STATIC VARIABLES
************************************/
static Binary_Tree _the_tree;

/*********************************** 
        FUNCTIONS
************************************/
/*********************************** 
    FUNCTION:init_binary_tree()
************************************/
void init_binary_tree(void)
{
  memset( &_the_tree, 0, sizeof(Binary_Tree) );
} /* init_binary_tree */

/*********************************** 
    FUNCTION:size()
************************************/
uint size(void)
{
  uint retVal = _the_tree._size;
  return retVal;
} /* size */

/*********************************** 
    FUNCTION:insert_element
************************************/
bool insert_element
(
  int element
)
{
  bool retVal;

  /*===========================================================*/

  if( _the_tree._root_ptr != NULL )
  {
    retVal = insert_element_internal( element, _the_tree._root_ptr );
  }
  else
  {
    Node *tmp_node_ptr  = (Node *)malloc( sizeof(Node) );
    _the_tree._root_ptr = tmp_node_ptr;
    tmp_node_ptr->_element = element;
    tmp_node_ptr->_left_node_ptr = NULL;
    tmp_node_ptr->_right_node_ptr = NULL;
    retVal = true;
  }

  if ( retVal = true)
  {
    _the_tree._size++;
  }

  return retVal;
} /* insert_element */

/*********************************** 
    FUNCTION:delete_element
************************************/


/*********************************** 
    FUNCTION:find_element
************************************/
Node* find_element
(
  int element
)
{
  return find_element_internal(element, _the_tree._root_ptr);
} /* find_element */


/****************************************** 
          INTERNAL FUNCTIONS
*******************************************/
/*********************************** 
    FUNCTION:insert_element_internal
************************************/
bool insert_element_internal
(
  int element,
  Node* node_ptr
)
{
  bool retVal = false;

  /*===========================================================*/

  if( element < node_ptr->_element )
  {
    if( node_ptr->_left_node_ptr != NULL )
    {
      retVal = insert_element_internal( element, node_ptr->_left_node_ptr );
    }
    else /* node_ptr->_left_node_ptr == NULL */
    {
      Node *tmp_node_ptr  = (Node *)malloc( sizeof(Node) );

      node_ptr->_left_node_ptr = tmp_node_ptr;

      tmp_node_ptr->_element = element;

      /* Sets the left child of the child node to null */
      tmp_node_ptr->_left_node_ptr = NULL;

      /* Sets the right child of the child node to null */
      tmp_node_ptr->_right_node_ptr = NULL;

      retVal = true;
    }  
  }
  else if( element > node_ptr->_element)
  {
    if( node_ptr->_right_node_ptr != NULL )
    {
      retVal = insert_element_internal( element, node_ptr->_right_node_ptr );
    }
    else /* node_ptr->_right_node_ptr == NULL */
    {
      Node *tmp_node_ptr  = (Node *)malloc( sizeof(Node) );

      node_ptr->_right_node_ptr = tmp_node_ptr;

      tmp_node_ptr->_element = element;

      /* Sets the left child of the child node to null */
      tmp_node_ptr->_left_node_ptr = NULL;

      /* Sets the right child of the child node to null */
      tmp_node_ptr->_right_node_ptr = NULL;

      retVal = true;
    }
  }
  else /* node_ptr->_element == _element*/
  {
    retVal = false;
  }

  return retVal;
} /* insert_element_internal */

/*********************************** 
    FUNCTION:find_element_internal
************************************/
Node* find_element_internal
(
  int element, 
  Node *node_ptr
)
{
  if( node_ptr != NULL )
  {
    if( element == node_ptr->_element )
    {
      return node_ptr;
    }
    if( element < node_ptr->_element )
    {
      return find_element_internal(element, node_ptr->_left_node_ptr);
    }
    else
      return find_element_internal(element, node_ptr->_right_node_ptr);
  }
  else return NULL;
} /* find_element_internal */

